1. Field of the Invention
The present invention relates to an apparatus for refining a determination rule in a decision tree form that is applicable for various fields such as machine control in manufacturing fields, demand prediction in service fields, and trouble diagnoses for estimating causes of machine defects and that evaluates given data, a method thereof and a medium thereof.
2. Description of the Related Art
As a method for representing a determination rule used to evaluate given data, a decision tree is known. The decision tree is composed of branch nodes, end nodes, and branches. Attributes that represent characteristics of data are assigned to the branch nodes. Category classes that represent decisions given to data are assigned to the end nodes. The branches are labeled with conditions of attribute values that link nodes.
As a method for learning a determination rule in a decision tree form, for example, ID3 algorithm is known (see "Artificial Intelligence Handbook", Kyoritsu Shuppan K. K., Vol 3, Page 529, 1984). In the ID3 algorithm, an attribute is selected corresponding to mutual information and a training instance is divided with the selected attribute. By connecting the divided partial training instance and a node corresponding to the original training instance, the determination rule in the decision tree form is grown. In addition, in the ID3 algorithm, by giving an evaluation object to the generated decision tree, the feature amount of the evaluation object can be estimated.
However, the ID3 does not include a function for refining a decision tree. Thus, to learn a decision tree corresponding to a newly obtained instance, the decision tree should be relearnt with a training instance used to learn the decision tree and the newly obtained training instance. Thus, to relearn a decision tree, a memory with a large storage capacity is required so as to store a large number of training instances. In addition, since the past learnt result is not used for relearning a decision tree, training instances should be learnt once again from the beginning. Thus, it takes a long time.
As another method for learning a determination rule in a decision tree form, ID5R algorithm is known. The ID5R algorithm is described in for example "P. E. Utgoff, Incremental Induction of Decision Trees," Machine Learning, No. 4, P.P. 161-181, 1989. In the ID5R algorithm, when a new example is given, an evaluation value for determining whether or not an attribute assigned to a branch node is proper. When an attribute with the best evaluation value has not been assigned to the branch node, the attribute assigned to the branch node is changed to an attribute with the best evaluation value and a partial decision tree that follows the branch node is updated. In other words, in the ID5R algorithm, since a decision tree is refined with the past learnt results, the time-related problem is improved in comparison with the ID3 algorithm.
However, the refinement of a decision tree in the ID5R algorithm is performed with an assumption that instances are progressively given. Thus, it is not taken thought of a method to refine instance for refining the decision tree. In addition, when it is determined whether or not an attribute assigned to a branch node is proper, a training instance that has been used to learn the decision tree is required. Thus, as with the case of the ID3 algorithm, in the ID5R algorithm, a memory with a large storage capacity that stores a large number of training instances is required.